# -*- coding: utf-8 -*-

"""剑指 Offer II 097. 子序列的数目
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。

示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：
0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成"""


class Solution:
    """遇到子序列，用矩阵，martrix表示子序列与主序列各位置是否一样
      r a b b b i t --j
    r 1 0 0 0 0 0 0
    a 0 1 0 0 0 0 0
    b 0 0 1 1 1 0 0
    b 0 0 1 1 1 0 0
    i 0 0 0 0 0 1 0
    t 0 0 0 0 0 0 1
    |i
    计算子序列的条数，就是统计走到最后一行t为真值的所有路径，走法讲究，从第1行真值出发，到下一行的右侧找真值；
    到每个点的有效路径条数是固定的，且有走法指导，下一行的路径数可以用上一行的路径数推演出来。
    设 f(i, j) 为到第i行，j列处的路径数，初始值为0
    f(i,j) = sum(f(i-1, 0), f(i-1, 1)...f(i-1, j-1))+common(i, j)
    answer = sum(f(last, 0), f(last, 1)...f(last, last))
    
    直接将动态规划二维表套到匹配矩阵上还好实现些。
    """
    def numDistinct(self, s: str, t: str) -> int:
        if not t:
            return 1
        elif not s:
            return 0
        elif len(s) < len(t):
            return 0

        dp = [[0 for _ in range(len(s))] for _ in range(len(t))]
        for i, chi in enumerate(t):
            if i == 0:
                for j, chj in enumerate(s):
                    dp[i][j] = int(chi == chj)
                continue

            for j, chj in enumerate(s):
                comm = int(chi == chj)
                if comm:
                    dp[i][j] = sum(dp[i-1][0:j])
                else:
                    dp[i][j] = 0
        
        # for row in dp:
        #     for col in row:
        #         print(col, end=',')
        #     print('')
        
        return sum(dp[i])


if __name__ == '__main__':
    so = Solution()
    print(so.numDistinct(s = "rabbbit", t = "rabbit"))
    print(so.numDistinct(s = "babgbag", t = "bag"))
